#include "../include/string.h"

#include <memory.h>
#include <stdlib.h>

BOOL ConcatSString( SString *T, SString S1, SString S2 )
{
    BOOL uncat = TRUE;

    if ( S1[0] + S2[0] < MAXSTRSIZE ) {
        memcpy( &( ( *T )[1] ), &S1[1], S1[0] );
        memcpy( &( ( *T )[S1[0] + 1] ), &S2[1], S2[0] );
        ( *T )[0] = S1[0] + S2[0];
    } else if ( S1[0] < MAXSTRSIZE ) {
        memcpy( &( ( *T )[1] ), &S1[1], S1[0] );
        memcpy( &( ( *T )[S1[0] + 1] ), &S2[1], MAXSTRSIZE - S1[0] );
        ( *T )[0] = MAXSTRSIZE;
        uncat = FALSE;
    } else {
        memcpy( &( ( *T )[0] ), &S1[0], MAXSTRSIZE + 1 );
        uncat = FALSE;
    }

    return uncat;
}

Status CreateSString( SString *T, const char *pstr, size_t length )
{
    if ( length > MAXSTRSIZE ) {
        return ERROR;
    }

    memcpy( &( ( *T )[1] ), pstr, length );
    ( *T )[0] = ( unsigned char )length;

    return OK;
}

BOOL CmpSString( SString *S1, SString *S2 )
{
    int cur = 1;

    if ( ( *S1 )[0] != ( *S2 )[0] ) {
        return FALSE;
    }

    for ( cur = 1; cur <= ( *S1 )[0]; ++cur ) {
        if ( ( *S1 )[0] != ( *S2 )[0] ) {
            return FALSE;
        }
    }

    return TRUE;
}

Status SubString( SString *substr, SString S, size_t pos, size_t len )
{
    if ( pos < 1 || pos > ( size_t )S[0]
            || len < 0 || len > S[0] - pos + 1 ) {
        return ERROR;
    }

    memcpy( &( ( *substr )[1] ), &S[pos], len );
    ( *substr )[0] = ( unsigned char )len;
    return OK;
}

Status StrInsert( HString *S, int pos, HString T )
{
    int cur = 0;

    if ( pos < 1 || S->length + 1 < pos ) {
        return ERROR;
    }

    S->chs = ( char * )realloc( S->chs, S->length + T.length );

    if ( S->chs == NULL ) {
        return ERROR;
    }

    for ( cur = S->length - 1; cur >= pos - 1; ++cur ) {
        S->chs[cur + T.length] = S->chs[cur];
    }

    memcpy( &( S->chs[pos - 1] ), T.chs, T.length );
    S->length += T.length;

    return OK;
}

Status CreateHString( HString *T, const char *pstr, size_t length )
{
    if ( T->chs != NULL ) {
        free( T->chs );
        T->length = 0;
        T->chs = NULL;
    }

    T->chs = ( char * ) malloc( length );

    if ( T->chs == NULL ) {
        return ERROR;
    }

    memcpy( T->chs, pstr, length );
    T->length = ( int )length;

    return OK;
}

BOOL InitHString( HString *T )
{
    T->chs = NULL;
    T->length = 0;

    return TRUE;
}

size_t KMP( SString *S, SString *T, size_t pos )
{
    size_t i = pos;
    size_t j = 1;

    int *next = ( int * )malloc( sizeof( int ) * ( ( *T )[0] + 1 ) );
    GetNext( T, next );

    while ( i <= ( *S )[0] && j <= ( *T )[0] ) {
        if ( j == 0 || ( *S )[i] == ( *T )[i] ) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    if ( j > ( *T )[0] ) {
        return i - ( *T )[0];
    } else {
        return 0;
    }
}

void GetNext( SString *S, int *next )
{
    int i = 1;
    int j = 0;

    next[i] = 0;

    while ( i < ( *S )[0] ) {
        if ( j == 0 || ( *S )[i] == ( *S )[j] ) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

void get_nextval( const char *pSchema, int length, int *next )
{
    int i = 0;
    int j	= -1;
    next[0]	= -1;

    while ( i < length ) {
        if ( j == -1 || pSchema[i] == pSchema[j] ) {
            ++i;
            ++j;

            if ( pSchema[i] != pSchema[j] ) {
                next[i] = j;
            } else {
                next[i] = next[j];
            }
        } else {
            j = next[j];
        }
    }
}

int kmp( const char *pSrc, int nSrcLength,
         const char *pSchema, int nSchemaLength,
         int pos )
{
    int i = pos;
    int j = 0;

    int *next = ( int * )malloc( sizeof( int ) * nSchemaLength );
    memset( next, 0, sizeof( int )*nSchemaLength );
    get_nextval( pSchema, nSchemaLength, next );

    while ( i < nSrcLength && j < nSchemaLength ) {
        if ( j == -1 || pSrc[i] == pSchema[j] ) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    if ( j == nSchemaLength ) {
        return i - nSchemaLength;
    } else {
        return 0;
    }
}
